﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using UFPE.CIn.Abc.Primality.Util;
using System.Diagnostics;

namespace UFPE.CIn.Abc.Primality.Algorithms
{
    public class AKSL : BaseAlgorithm
    {
        private static AKSL instance;

        public static AKSL Instance
        {
            get
            {
                if (instance == null)
                {
                    instance = new AKSL();
                }

                return instance;
            }
        }

        public override bool Helper(BigInteger thisVal)
        {
            long val = Convert.ToInt64(thisVal.ToString());

            //if (IsPerfectPower(val))
            //{
            //    //Console.WriteLine("Caiu PP");
            //    return false;
            //}
            //Console.WriteLine("Passou PP");
            long r = calcularR(val);
            if (r == -1) return false;

            for (long i = 1; i <= r; i++) {
                long gcdAVal = Gcd(i, val);

                if (gcdAVal > 1 && gcdAVal < val)
                {
                    //Console.WriteLine("Caiu GCD");
                    return false;
                }
            }
            //Console.WriteLine("Passou GCD");

            Console.WriteLine("Valor de r: " + r);
            
            //if (val <= r)
            //{
            //    return true;
            //}

            double log2 = Math.Log(val, 2);
            long limite = (long) Math.Floor(Math.Sqrt(AKS.Euler(r)) * log2);

            for (long i = 1; i <= limite; i++)
            {
                //Console.WriteLine(i);
                //Stopwatch swTemp = Stopwatch.StartNew();
                Poly polyMod = new Poly(r);
                polyMod.coeficientes[r] = 1;
                polyMod.coeficientes[0] = -1;

                Poly fixedRightSide = new Poly(val);
                fixedRightSide.coeficientes[val] = 1;
                fixedRightSide.coeficientes[0] = i;

                Poly valRightSide = new Poly(0);
                valRightSide.coeficientes[0] = val;

                Poly leftSide = new Poly(i, 1);

                //swTemp.Stop();
                //Console.WriteLine(swTemp.ElapsedMilliseconds + "ms instanciando");
                //swTemp = Stopwatch.StartNew();
                
                Poly verifyEquality = (fixedRightSide % polyMod) % valRightSide;

                //swTemp.Stop();
                //Console.WriteLine(swTemp.ElapsedMilliseconds + "ms tirando modulo do lado direito");
                //swTemp = Stopwatch.StartNew();

                Poly modPow = (leftSide % polyMod) % valRightSide;
                for (long j = 0; j < val; j++)
                {
                    modPow = modPow * leftSide;
                    modPow = (leftSide % polyMod) % valRightSide;
                }

                //swTemp.Stop();
                //Console.WriteLine(swTemp.ElapsedMilliseconds + "ms fazendo modpow");

                if (modPow != verifyEquality)
                {
                    return false;
                }
            }
            return true;
        }

        public long calcularR(long val)
        {
            double log2 = Math.Log(val, 2);
            long log22n = (long) Math.Floor(Math.Pow(log2,2));
            BigInteger valB = val;

            long r = 2;

            while (r < val)
            {
                if (Gcd(r, val) != 1) return -1;
                
                for (long k = log22n; k <= r; k++)
                {
                    if (valB.modPow(k, r) == 1)
                    {
                        return r;
                    }
                }
                r++;
            }

            return r;
        }

        //private bool IsValidR(long r, long start, long n)
        //{
        //    long val = n % r;
        //    for (long i = 0; i < start; i++)
        //    {
        //        val *= n;
        //        val = val % r;
        //    }

        //    for (long k = start; k <= r; k++)
        //    {
        //        val *= n;
        //        val = val % r;

        //        if (val == 1)
        //        {
        //            return true;
        //        }
        //    }
        //    return false;
        //}

        public bool IsPerfectPower(long i)
        {
            long a = 2;

            double b;

            do {
                b = Math.Pow(i, (1D/a));
                if (Math.Floor(b) == Math.Ceiling(b))
                {
                    return true;
                }
                a++;
            }while(b >= 2);

            return false;
        }

        public long Gcd(long x, long y)
        {
            long g = y;

            while (x != 0)
            {
                g = x;
                x = y % x;
                y = g;
            }

            return g;
        }

        public override string AlgorithmName
        {
            get 
            { 
                return "AKS versão 6"; 
            }
        }

        public override long Threshold
        {
            get
            {
                return 1048583;
            }
        }
    }
}
